import java.util.ArrayList;
import java.util.List;

/**
 * 1909. 删除一个元素使数组严格递增
 * https://leetcode-cn.com/problems/remove-one-element-to-make-the-array-strictly-increasing/
 */
public class Solutions_1909 {
    public static void main(String[] args) {
        int[] nums1 = {1, 2, 10, 5, 7};  // output: true
        int[] nums2 = {2, 3, 1, 2};  // output: false
        int[] nums3 = {1, 1, 1};  // output: false
        int[] nums4 = {1, 2, 3};  // output: true
        int[] nums5 = {1, 4, 1, 2, 3};  // output: false

        List<int[]> inputs = new ArrayList<>();
        inputs.add(nums1);
        inputs.add(nums2);
        inputs.add(nums3);
        inputs.add(nums4);
        inputs.add(nums5);

        for (int[] input : inputs) {
            boolean result = canBeIncreasing(input);
            System.out.println(result);
        }
    }

    public static boolean canBeIncreasing(int[] nums) {
        int cnt = 0;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] <= nums[i - 1]) {
                // 此时需要移除 1 个元素
                // 关键：是移除 nums[i]，还是 nums[i - 1]
                // 贪心思想：如果 nums[i] >= nums[i - 2]，则删除 nums[i - 1]，否则删除 nums[i - 1]
                cnt ++;
                if (i > 1 && nums[i] <= nums[i - 2]) {
                    nums[i] = nums[i - 1];
                }
                if (cnt > 1) {
                    return false;
                }
            }
        }
        return true;
    }
}
